#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet; /* 默认元素为整数*/

int Min(int x, int y) {
    return (x < y) ? x : y;
}

/* 算法10-11：改进二路归并 TwoWayMergeImproved(a,t,l,m,r) */
void TwoWayMergeImproved(ElemSet *a, ElemSet *t, int l, int m, int r) {
    int i, j, k;

    i = l; /* 左子序列当前待比较的元素位置 */
    j = m + 1; /* 右子序列当前待比较的元素位置 */
    k = l; /* 结果序列当前待放入的元素位置 */
    while (i <= m || j <= r) {
        if (j > r || (i <= m && a[i] < a[j])) {
            t[k] = a[i];
            i++;
            k++;
        } else {
            t[k] = a[j];
            j++;
            k++;
        }
    }
}
/* 算法10-11 结束 */

/* 算法10-12：改进的自底向上归并排序 MergeSortBottomUpImproved(a,l,r) */
void MergeSortBottomUpImproved(ElemSet *a, int l, int r) {
    int sorted_len, n, l_x, r_x, r_y, count, i;
    ElemSet *t;

    sorted_len = 1; /* 当前有序子列长度 */
    n = r - l + 1; /* 待排元素个数，即序列长度 */
    t = (ElemSet *)malloc(sizeof(ElemSet) * n); /* 创建临时数组 */
    count = 0;
    while (sorted_len <
            n) { /* 当前有序子列长度小于序列长度，则相邻两子序列归并 */
        count++;
        l_x = l; /* 左子序列从最左端开始 */
        while (l_x <= r) {
            r_x = Min(l_x + sorted_len - 1, r); /* 左子序列的右端点 */
            r_y = Min(r_x + sorted_len, r); /* 右子序列的右端点 */
            if (count % 2 == 1) {
                TwoWayMergeImproved(a, t, l_x, r_x, r_y); /* a并入t */
            } else {
                TwoWayMergeImproved(t, a, l_x, r_x, r_y); /* t并入a */
            }
            l_x = r_y + 1; /* 下一对子序列的左子序列的左端点 */
        }
        sorted_len <<= 1; /* 有序子列长度加倍 */
    }
    if (count % 2 == 1) {
        for (i = l; i <= r; i++) { /* 将归并后的有序序列t复制回a中 */
            a[i] = t[i];
        }
    }
}
/* 算法10-12 结束 */

int main(void) {
    ElemSet *a; /* 数组a的下标从0开始 */
    int n, i;

    scanf("%d", &n);
    a = (ElemSet *)malloc(sizeof(ElemSet) * n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    MergeSortBottomUpImproved(a, 0, n - 1);
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }

    return 0;
}